import heapq
from typing import List


class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        segments.sort()

        ans = []

        start = 0
        now_color = 0
        colors = []

        for start1, end1, color1 in segments:
            # 处理之前已经结束的颜色段
            while colors and colors[0][0] < start1:
                end2, color2 = heapq.heappop(colors)
                if start != end2:
                    ans.append([start, end2, now_color])
                now_color -= color2
                start = end2

            # 处理当前新的颜色段之前的颜色段
            if now_color != 0 and start != start1:
                ans.append([start, start1, now_color])

            # 处理当前颜色段
            start = start1
            now_color += color1
            heapq.heappush(colors, [end1, color1])

            # print((start1, end1, color1), now_color, start, colors, ans)

        # 处理之前已经结束的颜色段
        while colors:
            end2, color2 = heapq.heappop(colors)
            if start != end2:
                ans.append([start, end2, now_color])
            now_color -= color2
            start = end2

        return ans


if __name__ == "__main__":
    print(Solution().splitPainting(segments=[[1, 4, 5], [4, 7, 7], [1, 7, 9]]))  # [[1,4,14],[4,7,16]]
    print(
        Solution().splitPainting(segments=[[1, 7, 9], [6, 8, 15], [8, 10, 7]]))  # [[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
    print(Solution().splitPainting(segments=[[1, 4, 5], [1, 4, 7], [4, 7, 1], [4, 7, 11]]))  # [[1,4,12],[4,7,12]]

    # 测试用例11/66
    print(Solution().splitPainting(segments = [[4,5,9],[8,12,5],[4,7,19],[14,15,1],[3,10,8],[17,20,18],[7,19,14],[8,16,6],[14,17,7],[11,13,3]]))